﻿// test_dfs.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
using namespace std;
int row, col;
int dir[4][2] = { {-1, 0}, {0, -1}, {1, 0}, {0, 1} };

// 从 x，y 出发 把可以走的地方都标记上
void Dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {   
    if (visited[x][y]) return;
    visited[x][y] = true;

    for (int i = 0; i < 4; i++)
    {
        int newx = x + dir[i][0];
        int newy = y + dir[i][1];
        if (newx < 0 || newx >= row || newy < 0 || newy >= col)
        {
            continue;
        }
        if (grid[x][y] < grid[newx][newy]) continue;

        Dfs(grid, visited, newx, newy);
    }
};

bool IsResult(vector<vector<int>>& grid, int x, int y)
{
    vector<vector<bool>> visited(row, vector<bool>(col, false));

    Dfs(grid, visited, x, y);

    bool isFirstRecord = false;
    bool isSecondRecord = false;

    //上
    for (int j = 0; j < col; j++)
    {
        if (visited[0][j]) isFirstRecord = true;
    }

    //左
    for (int i = 0; i < row; i++)
    {
        if (visited[i][0]) isFirstRecord = true;
    }

    //下
    for (int j = 0; j < col; j++)
    {
        if (visited[row-1][j]) isSecondRecord = true;
    }

    //右
    for (int i = 0; i < row; i++)
    {
        if (visited[i][col-1]) isSecondRecord = true;
    }
      
    return isFirstRecord && isSecondRecord;
}

vector<vector<int>> GetGrid()
{
    vector<vector<int>> grid;
    vector<int>row1 = { 1,3,1,2,4 };
    vector<int>row2 = { 1,2,1,3,2 };
    vector<int>row3 = { 2,4,7,2,1 };
    vector<int>row4 = { 4,5,6,1,1 };
    vector<int>row5 = { 1,4,1,2,1 };

    grid.push_back(row1);
    grid.push_back(row2);
    grid.push_back(row3);
    grid.push_back(row4);
    grid.push_back(row5);

    return grid;
}

int main()
{
    vector<vector<int>>grid = GetGrid();
    row = 5; col = 5;

    //bool result = IsResult(grid, 4, 0);
    //cout << result << endl;
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            if (IsResult(grid, i, j))
            {
                cout << i << ' ' << j << endl;
            }
        }
    }
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
